package golang

import "gitee.com/allowall-package/goutil/fn"

func MergeSort(a []int) []int {
	n := len(a)
	if n < 2 {
		return a
	}

	m := n / 2
	return Merge(MergeSort(a[:m]), MergeSort(a[m:]))
}

func Merge(l, r []int) []int {
	ln, rn := len(l), len(r)
	s := make([]int, 0)

	li, ri := 0, 0
	for li < ln && ri < rn {
		if l[li] > r[ri] {
			s = append(s, r[ri])
			ri++
		} else {
			s = append(s, l[li])
			li++
		}
	}

	if li < ln {
		s = append(s, l[li:]...)
	}

	if ri < rn {
		s = append(s, r[ri:]...)
	}

	return s
}

func MergeSortTest() {
	fn.SliceRand(a)
	fn.Dump(fn.FuncInfo(), a, MergeSort(a))
}
